package hihocode;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


//有某些位是残缺的，求最小的满足取余x等于y的数，如果没有输出No solution
public class AncientNumber {

//	public static void main(String[] args) {
//		Scanner scanner = new Scanner(System.in);
//		String number;
//		int x, y;
//		List<Integer> list;
//		while(scanner.hasNext()){
//			number = scanner.next();
//			x = scanner.nextInt();
//			list = new ArrayList<>();
//			y = scanner.nextInt();
//			int length = number.length();
//			StringBuilder sb = new StringBuilder();
//			//记录所有问号的下标
//			for(int i = 0; i < length; i++){
//				char c = number.charAt(i);
//				if(c == '?'){
//					list.add(i);
//				}else{
//					sb.append(c);
//				}
//			}
//			boolean res = getValue(sb, list, x, y, 0);
//			if(!res){
//				System.out.println("No solution");
//			}
//		}
//		scanner.close();
//	}
	
//	public static void main(String[] args) {
//		StringBuilder sb = new StringBuilder();
//		sb.append(1256);
//		List<Integer> list = new ArrayList<>();
//		list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);list.add(8);
//		System.out.println(getValue(sb, list, 0, 0, 0));
//	}
	
	//虽然不敢相信，但是这个竟然AC了
	public static boolean getValue(StringBuilder sb, List<Integer> list, int x, int y, int start){
		int size = list.size();
		boolean res = false;
		if(start == size){
			// System.out.println(sb.toString());
			BigInteger big = new BigInteger(sb.toString());
			res = big.mod(new BigInteger(x + "")).equals(new BigInteger(y + ""));
			if(res){
				System.out.println(sb.toString());
			}
			return res;
		}
		boolean first = list.get(start) == 0;
		for (int j = first ? 1 : 0; j <= 9; j++) {
			int index = list.get(start);
			sb.insert(index, j);
			res = getValue(sb, list, x, y, start + 1);
			if(res){
				return res;
			}
			sb.deleteCharAt(index);
		}
		return res;
	}
}
